Pairing

 ( Linear Algebra ) 

In mathematics, a pairing is an R-bilinear map from the Cartesian product of two R-modules, where the underlying ring R is Commutative ring.

---

Definition Let R be a commutative ring with unit, and let M, N and L be R-modules.

A pairing is any R-bilinear map $e:M\; \backslash times\; N\; \backslash to\; L$. That is, it satisfies

$e(r\backslash cdot\; m,n)=e(m,r\; \backslash cdot\; n)=r\backslash cdot\; e(m,n)$,

$e(m\_1+m\_2,n)=e(m\_1,n)+e(m\_2,n)$ and $e(m,n\_1+n\_2)=e(m,n\_1)+e(m,n\_2)$

for any $r\; \backslash in\; R$ and any $m,m\_1,m\_2\; \backslash in\; M$ and any $n,n\_1,n\_2\; \backslash in\; N$. Equivalently, a pairing is an R-linear map

$M\; \backslash otimes\_R\; N\; \backslash to\; L$

where $M\; \backslash otimes\_R\; N$ denotes the tensor product of M and N.

A pairing can also be considered as an R-linear map $\backslash Phi\; :\; M\; \backslash to\; \backslash operatorname\{Hom\}\_\{R\}\; (N,\; L)$, which matches the first definition by setting $\backslash Phi\; (m)\; (n)\; :=\; e(m,n)$.

A pairing is called perfect if the above map $\backslash Phi$ is an isomorphism of R-modules and the other evaluation map $\backslash Phi\text{'}\backslash colon\; N\backslash to\; \backslash operatorname\{Hom\}\_\{R\}(M,L)$ is an isomorphism also. In nice cases, it suffices that just one of these be an isomorphism, e.g. when R is a field, M,N are finite dimensional vector spaces and L=R.

A pairing is called non-degenerate on the right if for the above map we have that $e(m,n)\; =\; 0$ for all $m$ implies $n=0$; similarly, $e$ is called non-degenerate on the left if $e(m,n)\; =\; 0$ for all $n$ implies $m=0$.

A pairing is called alternating if $N=M$ and $e(m,m)\; =\; 0$ for all m. In particular, this implies $e(m+n,m+n)=0$, while bilinearity shows $e(m+n,m+n)=e(m,m)+e(m,n)+e(n,m)+e(n,n)=e(m,n)+e(n,m)$. Thus, for an alternating pairing, $e(m,n)=-e(n,m)$.

---

Examples Any scalar product on a real vector space V is a pairing (set , in the above definitions).

The determinant map (2 × 2 matrices over k) → k can be seen as a pairing $k^2\; \backslash times\; k^2\; \backslash to\; k$.

The Hopf map $S^3\; \backslash to\; S^2$ written as $h:S^2\; \backslash times\; S^2\; \backslash to\; S^2$ is an example of a pairing. For instance, Hardie et al.Hardie K.A.1; Vermeulen J.J.C.; Witbooi P.J., A nontrivial pairing of finite T0 spaces, Topology and its Applications, Volume 125, Number 3, 20 November 2002 , pp. 533–542. present an explicit construction of the map using poset models.

---

Pairings in cryptography In cryptography, often the following specialized definition is used:Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, SIAM J. of Computing, Vol. 32, No. 3, pp. 586–615, 2003.

Let $\backslash textstyle\; G\_1,\; G\_2$ be additive groups and $\backslash textstyle\; G\_T$ a multiplicative group, all of prime order $\backslash textstyle\; p$. Let $\backslash textstyle\; P\; \backslash in\; G\_1,\; Q\; \backslash in\; G\_2$ be generators of $\backslash textstyle\; G\_1$ and $\backslash textstyle\; G\_2$ respectively.

A pairing is a map: $e:\; G\_1\; \backslash times\; G\_2\; \backslash rightarrow\; G\_T$

for which the following holds:

1. Bilinearity: $\backslash textstyle\; \backslash forall\; a,b\; \backslash in\; \backslash mathbb\{Z\}:\backslash \; e\backslash left(aP,\; bQ\backslash right)\; =\; e\backslash left(P,\; Q\backslash right)^\{ab\}$
2. Non-degeneracy: $\backslash textstyle\; e\backslash left(P,\; Q\backslash right)\; \backslash neq\; 1$
3. For practical purposes, $\backslash textstyle\; e$ has to be computable in an efficient manner

Note that it is also common in cryptographic literature for all groups to be written in multiplicative notation.

In cases when $\backslash textstyle\; G\_1\; =\; G\_2\; =\; G$, the pairing is called symmetric. As $\backslash textstyle\; G$ is Cyclic group, the map $e$ will be commutative; that is, for any $P,Q\; \backslash in\; G$, we have $e(P,Q)\; =\; e(Q,P)$. This is because for a generator $g\; \backslash in\; G$, there exist integers $p$, $q$ such that $P\; =\; g^p$ and $Q=g^q$. Therefore $e(P,Q)\; =\; e(g^p,g^q)\; =\; e(g,g)^\{pq\}\; =\; e(g^q,\; g^p)\; =\; e(Q,P)$.

The Weil pairing is an important concept in elliptic curve cryptography; e.g., it may be used to attack certain elliptic curves (see MOV attack). It and other pairings have been used to develop identity-based encryption schemes.

---

Slightly different usages of the notion of pairing Scalar products on Complex number are sometimes called pairings, although they are not bilinear. For example, in representation theory, one has a scalar product on the characters of complex representations of a finite group which is frequently called character pairing.

---

See also

• Dual system
• Yoneda product

---

External links

• The Pairing-Based Crypto Library

Post Comment